def get_height(arbre):#hauteur = hauteur fils+1
  if len(arbre[1]) == 0 :
    return 1
  return 1 + max([get_height(fils) for fils in arbre[1]])

#
# search
#

def depth_first_search(tree, depth, l):
  l.append(tree)
  for son in tree[1]:
    depth_first_search(son, depth+1, l)

def locate_all_singleton(arbre):
  return locate_all_singleton_aux(arbre,[],[])

def locate_all_singleton_aux(arbre,l,pos_arbre):
  h = get_singleton_height_root(arbre)
  if h == 0 :
    for i,son in enumerate(arbre[1]):
      pos_son = pos_arbre+[i]
      l = locate_all_singleton_aux(son,l,pos_son)
    return l
  l.append((h,pos_arbre[:]))
  next_tree = arbre
  for i in xrange(0,h):
    next_tree = next_tree[1][0]
    pos_arbre.append(0)
  return locate_all_singleton_aux(next_tree,l,pos_arbre)

def get_singleton_height_root(arbre):
  if len(arbre[1])!=1:
    return 0
  else:
    return 1+get_singleton_height_root(arbre[1][0])

def get_max_singleton(arbre):
  l = locate_all_singleton(arbre)
  l.append((0,[0]))
  h_max = max(l)
  return h_max[0]

def get_all_max_singleton(tree):
  l = locate_all_singleton(tree)
  maxi = -1
  liste_max = []
  for h,coord in l:
    if h > maxi:
      maxi = h
      liste_max = [(h,coord)]
    elif h == maxi:
      liste_max.append((h,coord))
  return liste_max

def get_nb_elt_depth(tree, depth) :
  if depth == 0 :
    return 1
  else :
    s = 0
    for son in tree[1] :
      s += get_nb_elt_depth(son, depth-1)
    return s

def get_nb_elt_depth_forest(forest, depth) :
  s = 0
  for t in forest :
    s += get_nb_elt_depth(t,depth-1)
  return s

def tree_path2tree(tree,path) :
  res = tree
  for i in path :
    res = res[1][i]
  return res

def forest_path2tree(forest,path) :
  i = path[0]
  return tree_path2tree(forest[i],path[1:])

#
# Tree :: Get the n first elt at a given depth
#

def get_n_first_depth(tree,depth,n) :
  if depth == 0 :
    return [tree]
  else :
    l = []
    for son in tree[1] :
      r = get_n_first_depth(son, depth-1, n-len(l))
      for elt in r :
        l.append(elt)
        if len(l) == n :
          return l
    return l 

def get_nAtDepth(tree, n, depth) :
  history = []
  path = []
  get_nAtDepth_aux(tree, n, depth, path, history)
  return history

def get_nAtDepth_aux(tree, n, depth, path, history) :
  if depth == 0 :
    history.append(path)
    return
  for i,son in enumerate(tree[1]) :
    get_nAtDepth_aux(son, n, depth-1, path + [i], history)
    if len(history) == n :
      return

def get_nAtDepth_rev(tree, n, depth) :
  history = []
  path = []
  get_nAtDepth_rev_aux(tree, n, depth, path, history)
  return history

def get_nAtDepth_rev_aux(tree, n, depth, path, history) :
  if depth == 0 :
    history.append(path)
    return
  lt = len(tree[1])
  for i in xrange(lt) :
    ni = lt - i - 1
    son = tree[1][ni]
    get_nAtDepth_rev_aux(son, n, depth-1, path + [ni], history)
    if len(history) == n :
      return

#
# Forest :: Get the n first elt at a given depth
#

def get_nAtDepth_forest(forest, n, depth) :
  if depth == 0 :
    l = [[x] for x in xrange(min(n, len(forest)))]
    return l
  else :
    res = []
    i = 0
    for tree in forest :
      history = []
      get_nAtDepth_aux(tree, n-len(res), depth-1, [i], history)
      i += 1
      for path in history :
        res.append(path)
        if len(res) == n :
          return res
    return res

def get_nAtDepth_forest_rev(forest, n, depth) :
  lf = len(forest)
  if depth == 0 :
    l = []
    for i in xrange(lf) :
      ni = lf - i - 1
      l.append(ni)
    return l
  else :
    res = []
    i = 0
    for i in xrange(lf) :
      ni = lf - i - 1
      tree = forest[ni]
      history = []
      get_nAtDepth_rev_aux(tree, n-len(res), depth-1, [ni], history)
      i += 1
      for path in history :
        res.append(path)
        if len(res) == n :
          return res
    return res

def get_n_first_depth_forest(f,depth,n) :
  if depth == 0 :
    l = []
    for i,t in enumerate(f) :
      if i == n :
        return l
      l.append((i,t))
    return l
  else :
    l = []
    for i,t in enumerate(f) :
      res = get_n_first_depth(t,depth-1,n-len(l))
      for selected_tree in res :
        l.append((i,selected_tree))
        if len(l) == n :
          return l
    return l 

#
# Tree :: Get the first elt depth1 containing n others at depth2
#

def get_n_x_in_y(tree, depth1, depth2, n) :
  assert(depth1<depth2)
  new_depth = depth2-depth1
  return get_n_x_in_y_aux(tree, depth1, new_depth, n)

def get_n_x_in_y_aux(tree, d1, d2, n) :
  if d1 == 1 :
    l = []
    for son in tree[1] :
      res = get_n_first_depth(son, d2, n)
      l.append(son)
      n -= len(res)
      if n <= 0 :
        return l
    return l
  else :
    l = []
    for son in tree[1] :
      res = get_n_x_in_y_aux(son, d1-1, d2, n)
      l.append(son)
      n -= len(res)
      if n <= 0 :
        return l
    return l

def get_nXinY_path(tree, depth1, n, depth2) :
  assert(depth1<depth2)
  new_depth = depth2-depth1
  path = []
  history = get_nXinY_path_aux(tree, depth1, n, new_depth, path)
  return history

def get_nXinY_path_aux(tree, d1, n, d2, p) :
  if d1 == 0 :
    return []
  elif d1 == 1 :
    l = []
    for i,son in enumerate(tree[1]) :
      h = get_nAtDepth(son, n, d2)
      l.append(p+[i])
      n -= len(h)
      if n <= 0 :
        return l
    return l
  else :
    l = []
    for i,son in enumerate(tree[1]) :
      res = get_nXinY_path_aux(son, d1-1, n-len(l), d2, p+[i])      
      for r in res :
        l.append(r)
        if len(l) == n :
          return l
    return l

def get_nXinY_path_rev(tree, depth1, n, depth2) :
  assert(depth1<depth2)
  new_depth = depth2-depth1
  path = []
  history = get_nXinY_path_rev_aux(tree, depth1, n, new_depth, path)
  return history

def get_nXinY_path_rev_aux(tree, d1, n, d2, p) :
  if d1 == 0 :
    return []
  lt = len(tree[1])
  if d1 == 1 :
    l = []
    for i in xrange(lt) :
      ni = lt - i - 1
      son = tree[1][ni]
      h = get_nAtDepth_rev(son, n, d2)
      l.append(p+[ni])
      n -= len(h)
      if n <= 0 :
        return l
    return l
  else :
    l = []
    for i in xrange(lt) :
      ni = lt - i - 1
      son = tree[1][ni]
      res = get_nXinY_path_rev_aux(son, d1-1, n-len(l), d2, p+[ni])      
      for r in res :
        l.append(r)
        if len(l) == n :
          return l
    return l

#
# Forest :: Get the first elt depth1 containing n others at depth2
#

def get_n_x_in_y_forest(forest, depth1, depth2, n) :
  if depth1 == 0 :
    return [(i,forest) for i,forest in enumerate(forest)]
  else :
    l = []
    for i,t in enumerate(forest) :
      res = get_n_x_in_y(t, depth1-1, depth2-1, n-len(l))
      for selected_tree in res :
        l.append((i,selected_tree))
        if len(l) == n :
          return l
    return l

def get_nXinY_path_forest(forest, depth1, n, depth2) :
  if depth1 == 0 :
    l = []
    for i,tree in enumerate(forest) :
      res = []
      get_nAtDepth_aux(tree, n, depth2-1, [i], res)
      n -= len(res)
      l.append([i])
      if n == 0 :
        return l
    return l
  else : 
    l = []
    for i,tree in enumerate(forest) :
      res = get_nXinY_path_aux(tree, depth1, n-len(l), depth2, [i])
      l.extend(res)
      if len(l) == n :
        return l
    return l

def get_nXinY_path_forest_rev(forest, depth1, n, depth2) :
  lf = len(forest)
  if depth1 == 0 :
    l = []
    for i in xrange(lf) :
      ni = lf - i - 1
      tree = forest[ni]
      res = []
      get_nAtDepth_rev_aux(tree, n, depth2-1, [ni], res)
      n -= len(res)
      l.append([ni])
      if n == 0 :
        return l
    return l
  else : 
    l = []
    for i in xrange(lf) :
      ni = lf - i - 1
      tree = forest[ni]
      res = get_nXinY_path_rev_aux(tree, depth1, n-len(l), depth2, [ni])
      l.extend(res)
      if len(l) == n :
        return l
    return l


#
# print
#

def print_tree_list_path(tree, list_path) :
  l = [pprint(tree_path2tree(tree,p)) for p in list_path]
  return "\n".join(l)

def print_forest_list_path(forest, list_path) :
  l = [pprint(forest_path2tree(forest,p)) for p in list_path]
  return "\n".join(l)

def pprint(tree) :
  return pprint_aux(tree,0)

def pprint_aux(tree,depth) :
  i,sons = tree
  out = "%s[%s]%s"%("   "*depth,i,"\n")
  for s in sons :
     out += pprint_aux(s,depth+1)
  return out
